package leetcode.helper.tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 * @author Max
 * @date 2021年8月19日
 * @description 116.填充每个节点的下一个右侧节点指针 <br>
 */
public class Node {
	public int val;
	public Node left;// 双向链表
	public Node right;// 双向链表

	public Node next;// 双向链表
	public Node prev;// 双向链表
	public Node child;// 子链表

	public List<Node> children;// N叉树

	public Node random;

	public Node() {
	}

	public Node(int _val) {
		val = _val;
		this.next = null;
		this.random = null;
	}

	public Node(int _val, Node _left, Node _right, Node _next) {
		val = _val;
		left = _left;
		right = _right;
		next = _next;
	}

	public Node(int _val, List<Node> _children) {
		val = _val;
		children = _children;
	}

	/**
	 * 双向链表
	 *
	 * @param array
	 * @return
	 */
	public static Node array2tree(Integer[] array) {
		if (array == null || array.length == 0)
			return null;
		Node root = new Node();
		root.val = array[0];
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		int point = 1;
		int size = array.length;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			if (point < size) {
				Integer pi = array[point++];
				if (pi == null) {
					node.left = null;
				} else {
					Node left = new Node();
					left.val = pi;
					node.left = left;
					queue.add(left);
				}

			}
			if (point < size) {
				Integer pi = array[point++];
				if (pi == null) {
					node.right = null;
				} else {
					Node right = new Node();
					right.val = pi;
					node.right = right;
					queue.add(right);
				}
			}
		}
		return root;
	}

	public static Node array2tree1(Integer[] array) {
		if (array == null || array.length == 0)
			return null;
		Node root = new Node();
		root.val = array[0];
		Node p1 = root;
		Node p2 = root;
		int p = 1;
		while (p < array.length) {
			p1 = new Node();
			p1.val = array[p++];
			p1.prev = p2;
			p2.next = p1;
			p2 = p2.next;
		}
		return root;
	}

}
